# 一般计算问题
# 1.累加
# 计算1 + 2 + 3 + ... + n
# n = int(input())
# Sum = 0
# for i in range(1, n + 1):
#     Sum += i
# print(Sum)
# # 2.累乘
# # 计算n!
# n = int(input())
# result = 0
# for i in range(1, n + 1):
#     result *= i
# print(result)
# 3.定积分
# 计算f(x) = e**x在a到b上定积分的近似值
# import math
# a = int(input()) # 积分区间左边界
# b = int(input()) # 积分区间右边界
# num = int(input()) # 等分区间数量
# length = (b - a) / num # 等分区间长度
# x = a
# total_area = 0
# for i in range(0, num):
#     area = math.e**x * length
#     total_area += area
#     x += length
# print(total_area)
from operator import index

# 递推
# 1.顺推
# 求斐波那契数列第n项
# n = int(input())
# a = 1
# b = 1
# for i in range(3,n + 1):
#      c = a + b
#      a = b
#      b = c
# if n == 1 or n == 2:
#     print(f'斐波那契数列第{n}项是1')
# else:
#     print(f'斐波那契数列第{n}项是{c}')
# 逆推
# 猴子吃桃问题
# 猴子每天吃掉昨天剩下的一半多 1个桃子，第 10天只剩 1个，问猴子第一天摘了几个桃子？
# peach = [0] * 11 # 此处*11是为了让列表索引对应天数
# peach[10] = 1
# for i in range(9,0,-1):
#     peach[i] = 2 * (peach[i + 1] + 1)
# print(peach[1])

# 迭代
# 有数列 2/1,3/2,5/3,...,求数列的前 n项和。
# n = int(input())
# Sum = 2
# numerator = 2 # numerator 分子
# denominator = 1 # denominator 分母
# for i in range(n-1):
#     next_term = (numerator + denominator) / numerator # term 项
#     Sum += next_term
#     tmp = denominator
#     denominator = numerator
#     numerator += tmp
# print(f'数列的前n项和是{Sum}')
# 牛顿迭代法
# 求f(x) = x**2 -2的根的近似值
# x = 1 # x初始值可任选
# count = 0
# while count == 0 or abs(x - previous_x) >= 0.000001: # count == 0可以作为进入循环的初始条件
#     previous_x = x
#     function = x ** 2 - 2
#     derivative = 2 * x # derivative 导数
#     x = previous_x - function / derivative
#     count += 1
# print(f"f(x) = x**2 - 2的根的近似值是{previous_x}")

# 穷举
#公鸡 5元 1只,母鸡 3元 1只,小鸡 3只 1元.用 100元钱买 100只鸡,三种鸡都有.公鸡,母鸡,小鸡各买多少只刚好凑足 100元
# for rooster in range(1,20):
#     for hen in range(1, 33):
#         for chick in range(1,300):
#             if 100 == rooster + hen + chick and 100 == rooster*5 + hen*3 +chick*(1/3):
#                 print(f'公鸡{rooster}只,母鸡{hen}只,小鸡{chick}只')
#
# for rooster in range(1,20):
#     for hen in range(1, 33):
#         chick = 100 - rooster - hen
#         if 100 == rooster + hen + chick and 100 == rooster*5 + hen*3 +chick*(1/3):
#                 print(f'公鸡{rooster}只,母鸡{hen}只,小鸡{chick}只')

# 排序问题
# ls = [5, 8, 9, 4, 2]
# for i in range(len(ls) - 1):
#     for j in range(i + 1, len(ls)):
#         if ls[i] > ls[j]:
#             ls[i], ls[j] = ls[j], ls[i]
# print('升序后:',ls)

# 查找问题
# 顺序查找
# ls = [10, 30, 50, 70, 90, 110, 130, 150]
# target_data = int(input(''))
# for data in ls:
#     if target_data == data:
#         index = ls.index(data)
#         print(f'{target_data}在列表的第{index + 1}个位置')
#         break
# else:
#     print('未找到')

# 二分查找(数据量很大时查找效率高)
# ls = [10, 30, 50, 70, 90, 110, 130, 150]
# target_data = int(input(''))
# low, high = 0,len(ls) - 1
# while high >= low:
#     middle = (low + high) // 2
#     if ls[middle] == target_data:
#         print(f'{target_data}在列表的第{middle + 1}个位置')
#         break
#     elif ls[middle] > target_data:
#         high = middle - 1
#     else:
#         low = middle + 1
# else:
#     print('未找到')